package algorithm.graph;

import org.checkerframework.checker.units.qual.A;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * k 算法
 *
 * @author csp 2021-12-31
 */
public class Code04_Kruskal {

    public static class MySets {

        public HashMap<Node, List<Node>> setMap;

        public MySets(List<Node> nodes) {
            for (Node cur : nodes) {
                List<Node> set = new ArrayList<>();
                set.add(cur);
                setMap.put(cur, set);
            }
        }

        public boolean isSameSet(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);

            return fromSet == toSet;
        }

        public void union(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            for (Node toNode : toSet) {
                fromSet.add(toNode);
                setMap.put(toNode, fromSet);
            }
        }

    }

    /*--------------------------------------------*/

    static Comparator<Edge> edgeComparator = (o1,o2)->{
        return o1.weight - o2.weight;
    };

    /**
     * 最小生成树（？）
     * 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
     * [1]最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
     * （是不是相连不成环的意思）
     *
     * k 算法生成最小生成树
     *
     *
     * @param graph
     * @return
     */
    public static Set<Edge> kruskalMST(Graph graph) {
        MySets unionFind = new MySets(new ArrayList<>(graph.nodes.values()));

        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(edgeComparator);
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }
        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }

        return result;
    }












}
